#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
using namespace std;

struct TreeNode
{
    TreeNode* left;
    TreeNode* right;
    int _val;

    TreeNode(int val)
        :_val(val)
        ,left(nullptr)
        ,right(nullptr)
    {}
};

class Solution {
public:
    bool isTree(TreeNode* root, TreeNode* node)
    {
        if (root == nullptr)
            return false;
        if (root == node)
            return true;

        return (isTree(root->left, node))
            || (isTree(root->right, node));
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (p == root || q == root)
            return root;
        bool pLeft = isTree(root->left, p);  //1
        bool pRight = !pLeft;  // 0

        bool qLeft = isTree(root->right, q);  // 0
        bool qRight = !qLeft;  // 1
        if ((pLeft && qRight)
            || (qLeft && pRight))
        {
            return root;
        }

        if (pLeft && qLeft)
            return lowestCommonAncestor(root->left, p, q);
        if (pRight && qRight)
            return lowestCommonAncestor(root->right, p, q);
        return nullptr;
    }
};

int main()
{
    typedef TreeNode Node;

    Node* root = new Node(3);
    Node* n5 = new Node(5);
    Node* n1 = new Node(1);

    root->left = n5;
    root->right = n1;

    n5->left = new Node(6);
    n5->right = new Node(2);

    n5->right->left = new Node(7);
    n5->right->right = new Node(4);

    n1->left = new Node(0);
    n1->right = new Node(8);

    Solution t;
    t.lowestCommonAncestor(root, root->left, root->right);

    return 0;
}